一、metapath2vec [2017]

《metapath2vec: Scalable Representation Learning for Heterogeneous Networks》

1. 基于神经网络的模型可以表达潜在 embedding ，这些 embedding 可以捕获跨各种模式（如图像、音频、语言）的丰富、复杂数据的内部关系。社交网络 （social network ）和信息网络 （information network ）同样是丰富、复杂的数据，它们对人类交互（ human interaction ）的动态性 （dynamic）和类型（ type ）进行编码，并且同样适用于使用神经网络的 representation learning 。具体而言，通过将人们选择好友和保持联系的方式映射为 social language，我们可以将 NLP 的最新进展自然地应用于 network representation learning，尤其是著名的 NLP 模型 word2vec 。最近的一些研究提出了 word2vec-based network representation learning 框架，例如 DeepWalk、LINE、node2vec 。这些 representation learning 方法不是手工设计的网络特征，而是能够从 raw network 中自动发现有用的、且有意义的 latent 特征。

   然而，到目前为止，这些工作都集中在同质网络（ homogeneous network ）（只有单一类型的节点、单一类型的关系）的 representation learning 上。但是，大量的社交网络和信息网络本质上是异质（heterogeneous ）的，涉及多种类型的节点、以及多种类型的关系。这些异质网络（heterogeneous network ）提出了独特的挑战，而这些挑战是专门为同质网络设计的 representation learning 模型所无法处理的。以异质学术网络（ heterogeneous academic network ）为例：我们如何在作者（author）、论文（paper）、会议 （venue ）、组织（organization ）等多种类型的节点之间有效地保留 word-context 概念？随机游走（如 DeepWalk 和 node2vec 中所使用的的）能否可以应用于多种类型节点的网络？我们可以直接将面向同质网络的 embedding 架构（如 skip-gram）应用于异质网络吗？

   通过解决这些挑战，latent heterogeneous network embedding 可以进一步应用于各种网络挖掘任务，如节点分类、节点聚类、相似节点搜索。与传统的 meta-path-based 方法相比，潜在空间 representation learning 的优势在于它能够在没有 connected meta-path 的情况下对节点之间的相似性进行建模。例如，如果两个 author 从未在同一个 venue 上发表过论文（假设一个人在 NIPS 上发表了 10 篇论文，另一个人在 ICML 上发表了 10 篇论文），则他们基于 APCPA 的 Path-Sim 相似度将为零。 但是，通过 network representation learning 可以自然地克服相似度为零这一缺点。

   论文 《metapath2vec: Scalable Representation Learning for Heterogeneous Networks》 形式化了异质网络 representation learning 问题，其目标是同时学习多种类型节点的低维潜在的 embedding 。论文介绍了 metapath2vec 框架及其扩展 metapath2vec++ 框架。metapath2vec 的目标是最大化同时保留给定异质网络的结构（structure ）和语义（semantic） 的可能性。在 metapath2vec 中，论文首先提出了异质网络中 meta-path based 随机游走，从而针对各种类型的节点生成具有网络语义 （network semantic ）的异质邻域（ heterogeneous neighborhood）。其次，论文扩展了 skip-gram 模型从而促进空间临近（geographically close ）节点和语义临近 （semantically close ）节点的建模。最后，论文开发了一种基于异质负采样（heterogeneous negative sampling ）的方法，称作 metapath2vec++，可以准确有效地预测节点的异质邻域。

   论文提出的 metapath2vec 和 metapath2vec++ 模型不同于传统的 network embedding 模型，后者专注于同质网络。具体而言，传统模型对不同类型的节点和不同类型的关系进行相同的处理，导致异质节点无法产生可区分的 representation ，正如论文在实验中所证明的那样。此外，metapath2vec 和 metapath2vec++ 模型在几个方面也与 Predictive Text Embedding: PTE 模型不同。

   • 首先，PTE 是一种半监督学习模型，它结合了文本数据的 label 信息。

   • 其次，PTE 中的异质性来自于 text network ，其中包含 word-word 链接、word-document 链接、word-label 链接。本质上，PTE 的原始输入是单词，输出是每个单词的 embedding，因此 PTE 并不是多种类型的对象。

   论文在下表中总结了这些方法的差异，其中列出了算法的输入，以及 《Pathsim: Meta path-based top-k similarity search in heterogeneous information networks》 中使用的相同两个 query 在 DBIS 网络的 top 5 相似搜索结果（每一列是一个 query 的结果）。通过对异质邻域建模并进一步利用异质负采样技术，metapath2vec++ 能够为两种类型的 query 实现最佳的 top 5 相似结果。

   

   下图展示了 16 个 CS 会议和每个领域的相应知名学者学到的 embedding （128 维）的 2D 投影（基于PCA ）可视化。值得注意的是，论文发现 metapath2vec++ 能够自动组织这两种类型的节点并隐式学习它们之间的内部关系，这由链接每个 pair 的箭头的相似方向和距离所展示。例如， metapath2vec++ 学习 J. Dean -> OSDI 以及 C. D. Manning -> ACL 。metapath2vec 也能够将每个 author-conference pair 紧密分组，例如 R. E. Tarjan 和 FOCS 。所有这些属性都无法从传统的 network embedding 模型中发现。

   

   总而言之，论文工作的贡献如下：

   • 形式化异质网络 representation learning 的问题，并确定由网络异质性带来的独特挑战。

   • 开发有效（effective） 的、高效（efficient） 的 network embedding 框架 metapath2vec & metapath2vec++ ，用于同时保留异质网络的结构相关性（ structural correlation ）和语义相关性（ semantic correlation ）。

   • 通过广泛的实验，证明了论文提出的方法在各种异质网络挖掘任务中的有效性和可扩展性，例如节点分类（相对于 baseline 提升 35% ~ 219%）和节点聚类（相对于 baseline 提升 13% ~ 16% ）。

   • 演示了 metapath2vec & metapath2vec++ 自动发现异质网络中不同节点之间的内部语义关系，而这种关系现有工作无法发现。

2. 相关工作：network representation learning 可以追溯到使用潜在因子模型进行网络分析和图挖掘任务，例如 factorization model 在推荐系统、节点分类（node classification ）、关系挖掘（relational mining） 、角色发现（role discovery ）中的应用。这一丰富的研究领域侧重于分解网络的 matrix/tensor 格式（例如，邻接矩阵），从而为网络中的节点或边生成潜在特征。然而，分解大型 matrix/tensor 的计算成本通常非常昂贵，并且还存在性能缺陷，这使得它对于解决大型网络中的任务既不实用、也不有效。

   随着深度学习技术的出现，人们致力于设计基于神经网络的 representation learning 模型。例如 Mikolov 等人提出了 word2vec 框架（一个两层神经网络）来学习自然语言中 word 的分布式 representation 。DeepWalk 在 word2vec 的基础之上提出，节点的 context 可以通过它们在随机游走路径中的共现 （co-occurrence） 来表示。形式上，DeepWalk 将随机游走 walker 放在网络上从而记录 walker 的游走路径，其中每条随机游走路径都由一系列节点组成。这些随机游走路径可以被视为文本语料库中的 sentence 。最近，为了使节点的邻域多样化，Node2Vec 提出了有偏随机游走 walker （一种广度优先 breadth-first 和宽度优先width-first 混合的搜索过程），从而在网络上产生节点路径。随着节点路径的生成，这两项工作都利用 word2vec 中的 skip-gram 架构来对路径中节点之间的结构相关性进行建模。

   此外，人们已经提出了几种其它方法来学习网络中的 representation 。特别地，为了学习 network embedding，LINE 将节点的 context 分解为一阶邻近性（friend 关系）、二阶邻近性（friend’ friend 关系），这进一步发展为用于嵌入文本数据的半监督模型 PTE 。

   我们的工作通过设计 metapath2vec 和 metapath2vec++ 模型来进一步研究这个方向，从而捕获具有多种类型节点的大型异质网络所表现出的结构相关性和语义相关性。这是以前的模型所无法处理的，并且我们将这些模型应用于各种网络挖掘任务。

1.1 模型

1.1.1 问题定义

1. 异质网络（Heterogeneous Network ）定义：异质网络是一个图 $G=(V,E,T)$$G=(V,E,T)$，其中每个节点 $v$$v$ 和每条边 $e$$e$ 分别关联一个映射函数：

   $$\varphi (v):V\to T_V\varphi (e):E\to T_E$$

   其中 $T_V$$T_V$ 表示节点类型，$T_E$$T_E$ 表示边的类型，且满足 $|T_V|+|T_E|>2$$|T_V| + |T_E| \gt 2$ 。

   例如可以用作者（ author:A）、论文（ paper:P）、会议 （venue:V）、组织（ organization:O ）作为节点类型来表示下图中的学术网络（academic network ）。其中边可以表示合作者关系（coauthor ） A-A、发表关系（publish ） A-P,P-V、附属关系（affiliation） O-A ，引用关系（reference ） P-P 。黄色虚线表示 coauthor 关系，红色虚线表示引用关系。

   

2. 异质网络 representation learning 问题：给定一个异质网络 $G$$G$ ，任务的目标是学习一个 $d$$d$ 维的 latent representation $\mathbf{X}\in {\mathbb{R}}^{|V|\times d}$$\mathbf X\in \mathbb R^{ |V|\times d}$ ，其中 $d\ll |V|$$d\ll |V|$ ，使得该 representation 能够捕获网络的结构关系以及语义关系。任务的输出是一个低维矩阵 $\mathbf{X}$$\mathbf X$，其第 $v$$v$ 行对应一个 $d$$d$ 维向量 ${\overrightarrow{\mathbf{x}}}_v\in {\mathbb{R}}^d$$\mathbf{\vec x}_v\in \mathbb R^d$ ，即顶点 $v$$v$ 的 embedding 。

   注意，尽管 $V$$V$ 中存在不同类型的节点，但是各种类型节点的 embedding 都被映射到相同的潜在空间中。学到的节点 embedding 可以应用于各种异质网络挖掘任务，如节点分类、节点聚类、相似节点搜索等。

   问题的挑战来自于网络异质性，其中很难直接应用同质的 language embedding 方法和同质的 network embedding 方法。network embedding 模型的基本假设是：在embedding 空间保持节点及其邻域（上下文context）之间的邻近性。但是在异质网络中，如何定义和建模 node–neighborhood 的概念？另外，我们如何优化 embedding 模型，其中该模型有效维护多种类型节点和关系的结构和语义？

1.1.2 metapath2vec

1. 我们提出了一个通用框架 metapath2vec，从而在异质网络中学习所需要的的 node representation 。metapath2vec 的目标是在考虑多种类型的节点和边的情况下最大化网络概率network probability。

2. 同质的 network embedding ：首先考虑 word2vec 模型及其在同质 network embedding 任务中的应用。给定一个文本语料库，Mikolov 等人提出 word2vec 来学习语料库中单词的分布式 representation。受此启发，DeepWalk 和 node2vec 旨在将文本语料库中的 word-context 概念映射到 network 中。这两种方法都利用随机游走来实现这一点，并利用 skip-gram 模型来学习 node representation ，这有助于在同质网络中预测节点的结构上下文（ structural context）（即局部邻域 local neighborhood）。通常，给定网络 $G=(V,E)$$G=(V,E)$，模型的目标是根据局部结构 （local structure ）来最大化网络概率：

   $$\arg \underset{\theta }{max}\prod _{v\in V}\prod _{c\in \mathcal{N}(v)}p(c\mid v;\theta )$$

   其中：

   • $\mathcal{N}(v)$$\mathcal N(v)$ 为网络 $G$$G$ 中节点 $v$$v$ 的邻域，它可以由不同的定义方式，如 $v$$v$ 的直接相连的顶点集合。

   • $p(c\mid v;\theta )$$p(c\mid v;\theta)$ 定义了给定节点 $v$$v$ 的条件下，上下文 $c$$c$ 出现的条件概率。

3. 为了对顶点的异质邻域建模，metapath2vec 引入了异质 skip-gram 模型 Heterogeneous Skip-Gram。为了将异质网络结构融合到异质 skip-gram 模型中，metapath2vec 引入了基于 meta-path 的随机游走。

4. 异质 skip-gram 模型：在 metapath2vec 中，给定异质网络 $G=(V,E,T)$$G=(V,E,T)$ ，其中 $T_V$$T_V$ 表示节点类型，$T_E$$T_E$ 表示边的类型，$|T_V|>1$$|T_V|\gt 1$。我们通过最大化给定节点 $v$$v$ 的条件下，异质上下文 ${\mathcal{N}}_t(v),t\in T_V$$\mathcal N_t(v),t\in T_V$ 的条件概率，使得 skip-gram 能够学习异质网络 $G$$G$ 的有效node representation ：

   $$\arg \underset{\theta }{max}\sum _{v\in V}\sum _{t\in T_V}\sum _{c_t\in {\mathcal{N}}_t(v)}\log p(c_t\mid v;\theta )$$

   $p(c_t\mid v;\theta )$$p(c_t\mid v;\theta)$ 通常由一个 softmax 函数定义：

   $$p(c_t\mid v;\theta )=\frac{\exp ({\overrightarrow{\mathbf{x}}}_{c_t}\cdot {\overrightarrow{\mathbf{x}}}_v)}{\sum _{u\in V}\exp ({\overrightarrow{\mathbf{x}}}_u\cdot {\overrightarrow{\mathbf{x}}}_v)}$$

   其中： ${\overrightarrow{\mathbf{x}}}_v$$\mathbf{\vec x}_v$ 为 $\mathbf{X}$$\mathbf X$ 的第 $v$$v$ 行，是节点 $v$$v$ 的 embedding 向量；${\overrightarrow{\mathbf{x}}}_{c_t}$$\mathbf{\vec x}_{c_t}$ 为异质上下文 $c_t$$c_t$ 的 embedding 向量。

   注意：

   • 这里 node embedding 和 context embedding 都是在同一个 embedding 空间中，它们共享 embedding 矩阵 $\mathbf{X}$$\mathbf X$ 。

   • 由于 $p(c_t\mid v;\theta )$$p(c_t\mid v;\theta)$ 与顶点类型 $t$$t$ 无关，仅仅和节点 pair $(v,c_t)$$(v,c_t)$ 有关，如果我们将 $\sum _{t\in T_V}\sum _{c_t\in {\mathcal{N}}_t(v)}$$\sum_{t\in T_V}\sum_{c_t\in \mathcal N_t(v)}$ 合并为 $\sum _{c\in \mathcal{N}(v)}$$\sum_{c\in \mathcal N(v)}$，则上式就是 DeepWalk 的目标函数。因此 metapath2vec 的目标函数和 metapath2vec 的目标函数是相同的，而且区别在于随机游走的方式不同。

   ${\mathcal{N}}_t(v)$$\mathcal N_t(v)$ 表示节点 $v$$v$ 的第 $t$$t$ 种类型的邻域节点。考虑下图的学术网络，其中author 节点 $a_4$$a_4$ 的邻域可以为：author 邻域 $a_2,a_3,a_5$$a_2,a_3,a_5$，venue 邻域$\{\text{ACL},\text{KDD}\}$$\{\text{ACL},\text{KDD}\}$ ，organization 邻域 $\{\text{CMU},\text{MIT}\}$$\{\text{CMU},\text{MIT}\}$ ，paper 邻域 $\{p_2,p_3\}$$\{p_2,p_3\}$ 。

   

   为了有效优化目标函数，Milkolov 等人引入了负采样，它从网络种随机采样相对较小的一组节点来代替 softmax 。metapath2vec 也采用了相同的负采样技术。给定一个负采样大小 $M$$M$ ，则定义：

   $$\log p(c_t\mid v;\theta )=\log \sigma ({\overrightarrow{\mathbf{x}}}_{c_t}\cdot {\overrightarrow{\mathbf{x}}}_v)+\sum _{m=1}^M{\mathbb{E}}_{u^{(m)}\sim P(u)}[\log \sigma (-{\overrightarrow{\mathbf{x}}}_{u^{(m)}}\cdot {\overrightarrow{\mathbf{x}}}_v)]$$

   其中：

   • $\sigma (x)=\frac{1}{1+\exp (-x)}$$\sigma(x) = \frac{1}{1 + \exp(-x)}$ 为 sigmoid 函数。

   • $P(u)$$P(u)$ 为预定义的节点分布函数，根据该分布来采样 $M$$M$ 个负采样节点 $u^{(m)}$$u^{(m)}$ 。metapath2vec 无视节点类型来构建节点的频率分布frequency distribution。

5. 基于 meta-path 的随机游走：如何有效的将网络结构转化为 skip-gram？在 DeepWalk 和 node2vec 中，这是通过将 random walker 在网络上结合一个邻域函数来遍历的节点路径来实现的。

   我们也可以将 random walker 放到异质网络中，从而生成多种类型节点的路径。在随机游走的第 $i$$i$ 步，我们定义转移概率 $p(v^{<i+1>}\mid v^{<i>})$$p(v^{<i+1>}\mid v^{<i>})$ 为：在节点 $v^{<i>}$$v^{<i>}$ 的邻域上的归一化概率分布，其中忽略节点类型。然后将生成的游走序列作为 node2vec 和 DeepWalk 的输入。但是， 《Pathsim: Meta path-based top-k similarity search in heterogeneous information networks》 证明了：异质随机游走偏向于高度可见的节点类型（即那些在路径中频繁出现的节点类型），以及中心节点（即那些出现频繁出现在关键路径中的节点）。有鉴于此，我们设计了基于 meta-path 的随机游走，从而生成能够捕获不同类型节点之间语义相关性和结构相关性的随机游走序列，从而有助于我们将异质网络结构转化为异质 skip-gram 。

   形式化地，一个 meta-path 范式 $\mathcal{P}$$\mathcal P$ 定义为一个路径：

   $$V_1\stackrel{R_1}{\to }{V}_2\stackrel{R_2}{\to }\cdots V_t\stackrel{R_t}{\to }{V}_{t+1}\stackrel{R_{t+1}}{\to }\cdots \stackrel{R_{l-1}}{\to }{V}_l$$

   其中：

   • $V_t$$V_t$ 为类型为 $t$$t$ 的节点集合，$R_t$$R_t$ 定义了类型为 $t$$t$ 的节点和类型为 $t+1$$t+1$ 的节点之间的关系。

   • $R=R_1\circ R_2\circ \cdots \circ R_{l-1}$$R=R_1\circ R_2\circ \cdots\circ R_{l-1}$ 定义节点类型 $V_1,\cdots V_l$$V_1,\cdots V_l$ 之间关系的一个组合。

   以下图为例：meta-path: APA 代表两个author （类型为 A ） 在同一论文（类型为 P） 上的 co-author 关系，meta-path: APVPA 代表两个author （类型为 A ）在同一个会议（类型为 V ）的不同论文（类型为 P）上的 co-venue 关系。

   

   先前的工作表明：异质信息网络中的许多数据挖掘任务都可以通过 meta-path 建模受益。这里我们展示如何利用 meta-path 来指导异质 random walker 。给定一个异质网络 $G=(V,E,T)$$G=(V,E,T)$ 以及一个 meta-path 范式 $\mathcal{P}$$\mathcal P$，在随机游走的第 $i$$i$ 步的转移概率定义为：

   $$\begin{array}{c}p(v^{<i+1>}\mid v_t^{<i>},\mathcal{P})=\{\begin{array}{ll}\frac{1}{|{\mathcal{N}}_{t+1}(v_t^{<i>})|},& (v^{<i+1>},v_t^{<i>})\in E,\varphi (v^{<i+1>})=t+1\\ 0，& (v^{<i+1>},v_t^{<i>})\in E,\varphi (v^{<i+1>})\ne t+1\\ 0,& (v^{<i+1>},v_t^{<i>})\notin E\end{array}\end{array}$$

   其中： $v_t^{<i>}\in V_t$$v_t^{<i>} \in V_t$ 表示第 $i$$i$ 步的节点；${\mathcal{N}}_{t+1}(v_t^{<i>})$$\mathcal N_{t+1}(v_t^{<i>})$ 表示顶点 $v_t^{<i>}$$v_t^{<i>}$ 的、类型为 $V_{t+1}$$V_{t+1}$ 的邻域节点。

   即，下一个节点仅在类型为 $t+1$$t+1$ 的邻域节点中选择。

   由于 $v^{<i+1>}\in V_{t+1}$$v^{<i+1>} \in V_{t+1}$，这意味着 random walker 必须根据预定义的 meta-path $\mathcal{P}$$\mathcal P$ 来游走。此外，通常meta-path 都是对称的，如 $V_1=V_l$$V_1= V_l$ ，因此有：

   $$p(v^{<i+1>}\mid v_l^{<i>})=p(v^{<i+1>}\mid v_1^{<i>})$$

   基于 meta-path 的随机游走策略可以确保不同类型节点之间的语义关系可以正确的合并到 skip-gram 中。如下图所示，假设上一个节点为 CMU，当前节点为 $a_4$$a_4$ 。在传统的随机游走过程中，下一个节点可能是 $a_4$$a_4$ 周围的节点 $\{a_2,a_3,a_5,p_2,p_3,\text{CMU}\}$$\{a_2,a_3,a_5,p_2,p_3,\text{CMU}\}$ 。但是在meta-path 的范式 OAPVPAO 下，下一个节点倾向于论文类型的节点 $\{p_2,p_3\}$$\{p_2,p_3\}$ （类型为 P），从而保持路径的语义。

   总体而言，metapath2vec 和 node2vec 都是在 DeepWalk 基础上针对随机游走策略的改进。

   

1.1.3 metapath2vec ++

1. metapath2vec 在创建点 $v$$v$ 的邻域 ${\mathcal{N}}_t(v)$$\mathcal N_t(v)$ 时，根据上下文节点的类型来区分节点 $v$$v$ 的上下文节点，但是它忽略了 softmax 函数中的节点类型信息。即：在给定节点 $v$$v$ 的条件下，为了推断来自邻域 ${\mathcal{N}}_t(v)$$\mathcal N_t(v)$ 中给定类型的上下文 $c_t$$c_t$ ，metapath2vec 实际上采用了所有类型的负样本，包括相同类型 $t$$t$ 的负样本，以及其它类型的负样本。

2. 异质负采样（heterogeneous negative sampling）：我们进一步提出 metapath2vec++ 框架，其中softmax 根据上下文 $c_t$$c_t$ 的类型进行归一化。具体而言， $p(c_t\mid v;\theta )$$p(c_t\mid v;\theta)$ 根据指定的节点类型 $t$$t$ 来调整：

   $$p(c_t\mid v;\theta )=\frac{\exp ({\overrightarrow{\mathbf{x}}}_{c_t}\cdot {\overrightarrow{\mathbf{x}}}_v)}{\sum _{u_t\in V_t}\exp ({\overrightarrow{\mathbf{x}}}_{u_t}\cdot {\overrightarrow{\mathbf{x}}}_v)}$$

   其中 $V_t$$V_t$ 为类型为 $t$$t$ 的节点集合。

   这样做时，metapath2vec++ 为 skip-gram 模型输出层中的每种邻域类型定义一组 softmax 分布。回想一下，在 metapath2vec、node2vec、DeepWalk 中，输出softmax 分布的维度等于网络的节点数量 $|V|$$|V|$。但是在 metapath2vec ++ 中，输出 softmax 分布的维度由类型为 $t$$t$ 的节点数量 $|V_t|$$|V_t|$ 决定。如下图所示给定节点 $a_4$$a_4$ ，metapath2vec ++ 输出四组softmax 分布，每一组分布对应于不同的邻域节点类型：会议V、作者 A、组织 O、论文 P 。$V_t$$V_t$ 给出了类型为 $t$$t$ 的节点集合，$V=V_V\cup V_A\cup V_O\cup V_P$$V=V_V\cup V_A\cup V_O\cup V_P$ 。$k_t$$k_t$ 给出了节点邻域中类型为 $t$$t$ 的邻居节点数量（也是窗口大小），$k=k_V+k_A+k_O+k_P$$k=k_V + k_A + k_O + k_P$ 。

   注意，这里对每种类型顶点指定各自不同的窗口大小。

   

   受到 PTE 的启发，metapath2vec 在负采样过程中同样可以根据邻居节点 $c_t$$c_t$ 的类型进行调整，因此有目标函数：

   $$\mathcal{L}=\log \sigma ({\overrightarrow{\mathbf{x}}}_{c_t}\cdot {\overrightarrow{\mathbf{x}}}_v)+\sum _{m=1}^M{\mathbb{E}}_{u_t^{(m)}\in P_t(u_t)}[\log \sigma (-{\overrightarrow{\mathbf{x}}}_{u_t^{(m)}}\cdot {\overrightarrow{\mathbf{x}}}_v)]$$

   其中 $P_t(u_t)$$P_t(u_t)$ 为类型为 $t$$t$ 的顶点的分布函数。

   上式的物理意义为：负采样仅在上下文 $c_t$$c_t$ 类型相同的节点集合 $V_t$$V_t$ 中进行，而不是在全部节点集合 $V$$V$ 中进行。

   目标函数的梯度为：

   $$\begin{array}{c}\frac{\partial \mathcal{L}}{\partial {\overrightarrow{\mathbf{x}}}_{u_t^{(m)}}}=\sigma ({\overrightarrow{\mathbf{x}}}_{u_t^{(m)}}\cdot {\overrightarrow{\mathbf{x}}}_v-{\mathbb{I}}_{c_t}\left[u_t^{(m)}\right])\times {\overrightarrow{\mathbf{x}}}_v\\ \frac{\partial \mathcal{L}}{\partial {\overrightarrow{\mathbf{x}}}_v}=\sum _{m=0}^M\sigma ({\overrightarrow{\mathbf{x}}}_{u_t^{(m)}}\cdot {\overrightarrow{\mathbf{x}}}_v-{\mathbb{I}}_{c_t}\left[u_t^{(m)}\right])\times {\overrightarrow{\mathbf{x}}}_{u_t^{(m)}}\end{array}$$

   其中 ${\mathbb{I}}_{c_t}\left[u_t^{(m)}\right]$$\mathbb I_{c_t}\left[u_t^{(m)}\right]$ 为一个示性函数，用于指示 $u_t^{(m)}$$u_t^{(m)}$ 是否为邻域上下文节点 $c_t$$c_t$ ，并且当 $m=0$$m=0$ 时 $u_t^{(m)}=c_t$$u_t^{(m)} = c_t$ 。

   最终可以通过随机梯度下降算法来对模型进行优化求解。

3. metapath2vec++ 算法：

   • 输入：

     • 异构网络 $G=(V,E,T)$$G = (V,E,T)$

     • 一个 meta-path 范式 $\mathcal{P}$$\mathcal P$

     • 每个顶点开始的游走序列的数量 $w$$w$

     • 每条游走序列的长度 $l$$l$

     • embedding 维度 $d$$d$

     • 邻域大小 $k$$k$ （即窗口大小）

   • 输出：顶点的 embedding 矩阵 $\mathbf{X}\in {\mathbb{R}}^{|V|\times d}$$\mathbf X\in \mathbb R^{ |V|\times d}$

   • 算法步骤：

     • 初始化 $\mathbf{X}$$\mathbf X$

     • 迭代 $i=1,2,\cdots ,w$$i=1,2,\cdots,w$ ，迭代步骤为：

       遍历图 $V$$V$ 中的每个顶点 $v$$v$ ，执行：

       $$\begin{array}{c}\text{MP}=\text{MetaPathRandomWalk}(G,\mathcal{P},v,l)\\ \mathbf{X}=\text{HeterogeneousSkipGram}(\mathbf{X},k,\text{MP})\end{array}$$

     • 返回 $\mathbf{X}$$\mathbf X$

4. MetaPathRandomWalk 算法：

   • 输入：

     • 异构网络 $G=(V,E,T)$$G = (V,E,T)$

     • 一个 meta-path 范式 $\mathcal{P}$$\mathcal P$

     • 当前顶点 $v$$v$

     • 每条游走序列的长度 $l$$l$

   • 输出：一条 meta-path 随机游走序列

   • 算法步骤：

     • 初始化：$\text{MP}[1]=v$$\text{MP}[1] = v$

     • 迭代 $i=1,2,\cdots ,l-1$$i=1,2,\cdots,l-1$ ，迭代过程为：

       根据 $p(v^{<i+1>}\mid v_t^{<i>},\mathcal{P})$$p(v^{<i+1>}\mid v_t^{<i>},\mathcal P)$ 采样顶点 $u$$u$ ，并记录 $\text{MP}[i+1]=u$$\text{MP}[i+1] = u$

     • 返回 $\text{MP}$$\text{MP}$

5. HeterogeneousSkipGram 算法：

   • 输入：

     • 当前的 $\mathbf{X}$$\mathbf X$

     • 邻域大小 $k$$k$

     • 随机游走序列 $\text{MP}$$\text{MP}$，以及它的长度 $l$$l$

   • 输出：更新后的 $\mathbf{X}$$\mathbf X$

   • 算法步骤：

     • 迭代 $i=1,2,\cdots ,l$$i=1,2,\cdots,l$ ，迭代步骤为：

       取出当前顶点 $v=\text{MP}[i]$$v=\text{MP}[i]$ , 对左侧的 $k$$k$ 个顶点、右侧的 $k$$k$ 个顶点共计 $2k$$2k$ 个顶点进行更新：

       $$\begin{array}{c}{c}_t=\text{MP}[j],max(0,i-k)\le j\le min(i+k,l),j\ne i\\ {\mathbf{X}}^{new}={\mathbf{X}}^{old}-\eta \frac{\partial \mathcal{L}}{\partial \mathbf{X}}\end{array}$$

       其中 $\eta$$\eta$ 为学习率。

6. 下图给出了异质学术网络heterogeneous academic network ，以及学习该网络embedding 的 metapath2vec/metapath2vec ++ 的 skip-gram 架构。

   • 图 a 的黄色虚线表示 co-author 关系，红色虚线表示论文引用关系。

   • 图 b 表示 metapath2vec 在预测 $a_4$$a_4$ 的上下文时，使用的 skip-gram 架构。其中 $|V|=12$$|V|=12$ 为节点数量，$a_4$$a_4$ 的邻居顶点包括 $\{\text{CMU},a_2,a_3,a_5,p_2,p_3,\text{ACL},\text{KDD}\}$$\{\text{CMU},a_2,a_3,a_5,p_2,p_3,\text{ACL},\text{KDD}\}$ ，窗口大小 $k=8$$k=8$ 。

   • 图 c 表示 metapath2vec ++ 在预测 $a_4$$a_4$ 的上下文时，使用的 skip-gram 架构。metapath2vec++ 中使用异质 skip-gram。在输出层中，它不是为邻域中所有类型的节点指定一组多项式分布，而是为邻域中每种类型的节点指定各自的一组多项式分布。$V_t$$V_t$ 给出了类型为 $t$$t$ 的节点集合，$V=V_V\cup V_A\cup V_O\cup V_P$$V=V_V\cup V_A\cup V_O\cup V_P$ 。$k_t$$k_t$ 给出了节点邻域中类型为 $t$$t$ 的邻居节点数量（也是窗口大小），$k=k_V+k_A+k_O+k_P$$k=k_V + k_A + k_O + k_P$ 。

   注：我们可以指定多个 metapath，针对每个 metapath 学到对应的 embedding，最后将所有 embedding 聚合起来从而进行 metapath ensemble 。

   

7. 未来方向：

   • metapath2vec/metapath2vec++ 模型和 DeepWalk/node2vec 一样，在对网络采样生成大量随机游走路径时，面临大量中间临时输出数据的挑战。因此识别和优化采样空间是一个重要方向。

   • 和所有基于 meta-path 异质网络挖掘方法一样，可以通过自动学习有意义的 meta-path 来进一步改善 metapath2vec/metapath2vec++ 。

   • 扩展模型从而融合演变中的异质网络的动态性 dynamic 。

   • 将模型泛化到不同风格genre 的异质网络。

1.2 实验

1. 这里我们展示了 metapath2vec/metapath2vec ++ 用于异质网络 representation learning 的效果和效率。我们评估了经典的三种异质网络挖掘任务，包括：节点分类问题、节点聚类问题、相似节点搜索问题。

   另外，我们还通过 tensorflow 的 embedding 可视化来观察异质学术网络中学到的节点 embedding 。

2. 数据集：我们使用以下两个异质网络，它们都是公开的：

   • AMiner Computer Science(CS) dataset：包含 2016 年之前j举行的 3883 个计算机科学venue（包含会议 conference 和期刊 journal ）的 9323739 名计算机科学家，以及 3194405 篇论文。我们构建了一个异质网络，该网络包含三种类型的节点： author:A、 paper:P、venue:V 。不同类型节点之间的链接代表不同的关系。

   • Database and Information Systems(DBIS) dataset：包含 464 个会议，以及其中 top-5000 个作者，以及对应的 72902 篇论文。我们也构建了一个异质网络，该网络包含三种类型的节点： author:A、 paper:P、venue:V 。

3. baseline 方法：我们将 metapath2vec/metapath2vec ++ 和以下几种最近的网络 representation learning方法进行比较：

   • DeepWalk/node2vec ：在相同的随机游走序列输入下，我们发现 DeepWalk 的hierarchical softmax 和 $p=1,q=1$$p=1,q=1$ 的 node2vec 的负采样之间并未产生显著差异，因此我们这里采用 $p=1,q=1$$p=1,q=1$ 的 node2vec 。

   • LINE：我们使用同时采用了1 阶邻近性和 2 阶邻近性的 LINE 模型。

   • PTE：我们构建了三个异质二部图 A-A, A-V, V-V ，并将其作为无监督 embedding 学习方法的约束。

   • 谱聚类（Spectral Clustering）/图因子分解（ Graph Factorization）：因为早前的研究表明 DeepWalk 和 LINE 的性能超越了它们，因此这里并不考虑这两种方法。

4. 参数配置：对于所有模型，我们使用以下相同的参数：

   • 每个顶点开始的随机游走序列数量 $w=1000$$w=1000$ 。

   • 每个随机游走序列长度 $l=100$$l=100$ 。

   • 隐向量维度 $d=128$$d=128$ 。注意：对于 LINE 模型，其一阶embedding 和 二阶 embedding 的维度都是 128 。

   • 邻域size $k=7$$k=7$ 。

   • 负采样size $M=5$$M=5$

   • 对于 metapath2vec/metapath2vec ++ ，我们还需要指定 meta-path 范式来指导随机游走的生成。我们调查了大多数基于 meta-path 的工作，发现异质学术网络中最常用和有效的meta-path 范式是 APA 和 APVPA 。注意，APA 表示 co-author 语义，即传统同质网络的 collaboration 关系；APVPA 代表两个 author 在同一个 venue 发表了论文（可以是不同的论文）的异质语义。我们的实验表明：meta-path 范式 APVPA 产生的节点 embedding 可以泛化到各种异质学术网络的挖掘任务中。

   最后，在参数敏感性实验中，我们对参数中的一个进行变化，同时固定其它参数来观察 metapath2vec/metapath2vec ++ 的效果。

1.2.1 节点分类

1. 我们使用第三方的 label 来确定每个顶点的类别。

   • 首先将 Google Scholar 中的八个会议的研究类别与 AMiner 数据中的会议进行匹配：

     Computational Linguistics, Computer Graphics, Computer Networks & Wireless Communication, Computer Vision & Pattern Recognition, Computing Systems, Databases & Information Systems, Human Computer Interaction, Theoretical Computer Science
     

     每种类别20 个会议。在这 160 个会议中，有 133 个已经成功匹配并进行相应的标记。每篇论文标记为它所属会议的类别。

   • 然后，对于这 133 个会议的论文的每位作者，将他/她分配给他/她大部分论文的类别，如果论文类别分布均匀则随机选择一个类别。最终有 246678 位作者标记了研究类别。

2. 我们从完整的 AMiner 数据集中学到节点的 embedding ，然后将上述节点标记以及对应的节点 embedding 一起作为逻辑回归分类器的输入。

   我们将训练集规模从标记样本的 5% 逐渐增加到 90% ，并使用剩下顶点进行测试。我们将每个实验重复十轮，并报告平均的 macro-F1 和 micro-F1 。

   下表给出了 Venue 类型顶点的分类结果。

   

   下表给出了 Author 类型顶点的分类结果：

   

   结论：

   • metapath2ve/metapath2vec ++ 模型始终一致且明显的优于所有其它基准方法。

   • 在预测 Venue 类型节点的类别时，在训练数据量较小的情况下，metapath2vec/metapath2vec ++ 的优势特别明显。例如，给定 5% 的节点作为训练集，相对于 DeepWalk/node2vec, LINE, PTE，metapath2vec/metapath2vec++ 在 Macro-F1 方面实现了 0.08 ~ 0.23 的绝对提升（相对提升 35% ~ 319%），在 Micro-F1 方面实现了 0.13 ~ 0.26 的绝对提升（相对提升 39% ~ 145% ）。

   • 在预测 Author 类型节点的类别时，每种方法的性能在不同训练集规模情况下都相对稳定metapath2vec/metapath2vec ++ 相对LINE 和 PTE 稳定提升 2% ~ 3%、比 DeepWalk/node2vec 稳定提升 ~20% 。

   总之，通过多分类性能评估，metapath2vec/metapath2vec++ 学到的异质 node embedding 比当前 SOTA 的方法要好得多。metapath2vec/metapath2vec++ 方法的优势在于它们对网络异质性挑战（包含多种类型节点和多种类型边）的适当考虑和适应。

3. 我们接下来对 metapath2vec ++ 的几个通用参数进行超参数敏感性分析。我们变化其中的一个超参数，然后固定其它的超参数。

   结论：

   • 从图 a 和 b 可以看到，参数 $w$$w$ 和 $l$$l$ 对于 author 节点的分类性能是正向的，其中 $w=1000$$w=1000$ 、$l=100$$l=100$ 左右，author 节点分类性能提到到峰值附近。

     但是令人惊讶的是，$w,l$$w,l$ 对于 venue 节点的分类性能无关。

   • 从图 c 和 d 可以看到，embedding 尺寸 $d$$d$ 和邻域大小 $k$$k$ 与 venue 节点分类性能无关。而 $k$$k$ 对于 author 节点分类性能至关重要，下降的曲线表明较小的邻域大小对于 author 节点能够产生更好的 embedding 表示。这和同质图完全不同。在同质图中，邻域大小 $k$$k$ 通常对节点分类显示出正向影响，而这里是负向影响。

   • 根据分析，metapath2vec++ 对这些参数并不严格敏感，并且能够在 cost-effective 超参数选择的条件下（选择范围越小则效率越高）达到高性能。此外，我们的结果还表明，这些通用的超参数在异质网络中表示出和同质网络中不同的效果，这表明对于异质网络 representation learning需要采用不同的思路和解决方案。

   

1.2.2 节点聚类

1. 我们采用与上述分类任务中使用的相同的八个类别的 author 节点和 venue 节点（AMiner CS 数据集），我们针对这些节点的 embedding 进行聚类。这里我们使用 k-means 聚类算法，并通过归一化的互信息 NMI 来评估聚类效果。

   给定随机变量 $X,Y$$X,Y$ ，则归一化的互信息定义为：

   $$\text{NMI}(X;Y)=\frac{I(X;Y)}{H(X)}=\frac{H(X)-H(X\mid Y)}{H(X)}=\frac{\sum _x\sum _{y}p(x,y)\log \frac{p(x,y)}{p(x)\times p(y)}}{-\sum _{x}p(x)\log x}$$

   所有聚类实验均进行十次，并报告平均性能，结果如下表所示。结论：

   • 总体而言，metapath2vec 和 metapath2vec ++ 优于其它所有方法。

   • 从 venue 节点聚合结果可以看到，大多数方法（除了 DeepWalk/node2vec ）的NMI 都较高，因此该任务相对容易。但是我们的方法比LINE 和 PTE 高 2% ~ 3% 。author 节点聚类指标都偏低，因此任务更难。但是我们的方法相比最佳baseline （LINE 和 PTE）上获得更显著的增益：大约提升 13% ~ 16% 。

   总之，和 baseline 相比，metapath2vec 和 metapath2vec ++ 为网络中不同类型的节点生成了更合适的 embedding，这表明它们能够捕获和整合异质网络中各种类型节点之间的底层结构关系和语义关系。

   

2. 和分类实验的步骤相同，我们研究了聚类任务中 metapath2vec ++ 的参数敏感性，衡量指标为 NMI 。

   • 从图 a 和 b 可以看到，author 节点和 venue 节点在 $l=100,w=800\sim 1000$$l=100, w=800\sim 1000$ 时可以在效果和计算效率之间取得平衡。增加 $w$$w$ 和 $l$$l$ 对 author 节点的聚类结构正向影响，但是对 venue 节点影响不大。

   • 从图 c 和 d 可以看到，对于 author 节点，$d$$d$ 和 $k$$k$ 与聚类性能呈负面影响；而对于venue 节点，$d$$d$ 也与聚类性能负面影响，但是$k$$k$ 增加时聚类 NMI 先增加后减小。

     所有这些意味着对于 author 节点和 venue 节点，当 $d=128,k=7$$d=128,k=7$ 时，生成的 embedding 可以得到较好的聚类结果。

   

1１.2.3 相似节点搜索

1. 我们从 AMiner 数据集选择 16 个不同领域的顶级 CS 会议，然后通过余弦相似度选择这些会议节点的 top 10 相似度结果。结论：

   • 对于query 节点 ACL，metapath2vec++ 返回的venue 具有相同的主题 NLP ，如 EMNLP(1st)、NAACL(2nd)、Computational Linguistics(3rd)、CoNLL(4th)、COLING(5th) 等等。

     其它领域的会议的 query 也有类似的结果。

   • 大多数情况下，top3 结果涵盖了和 query 会议声望类似的venue。例如theory理论领域的 STOC 和 FOCS、system系统领域的 OSDI 和 SOSP、architecture 架构领域的HPCA 和 ISCA、security 安全领域的 CCS 和 S&P、human-computer interaction 人机交互领域的 CSCW 和 CHI、NLP 领域的 EMNLP 和 ACL、machine learning 机器学习领域的 ICML 和 NIPS、web 领域的 WSDM 和 WWW、artificial intelligence 人工智能领域的 AAAI 和 UCAI、database 数据库领域的 PVLDB 和 SIGMOD 等等。

   

2. 类似的，我们从 DBIS 数据中选择另外的 5 个 CS 会议，然后通过余弦相似度选择这些会议节点的 top 10 相似度结果。结论也类似。

   

3. 我们从 DBIS 数据中选择一个会议节点、一个作者节点，然后比较不同 embedding 方法找出的 top-5 相似度的结果。结果如下表所示，其中 metapath2vec ++ 能够针对不同类型的 query 节点获得最佳的 top-5 相似节点。

   

1.2.4 可视化

1. 我们使用 tensorflow embedding 2 维 PCA 来进一步可视化模型学到的节点 embedding 。我们从 AMiner CS 数据集选择 16 个不同领域的顶级 CS 会议，以及对应的顶级作者进行可视化。

   • 从图 d 可以看到，metapath2vec++ 能自动组织这两种类型的节点，并隐式学习它们的内部关系。这种内部关系可以通过连接每对节点的箭头的方向和距离表示，如 J.Dean --> OSDI，C.D.Manning --> ACL，R.E.Tarjan --> FOCS，M.I.Jordan --> NIPS 等等。

     这两类节点位于两个独立的“列”中，很显然图 a 和 b 的 embedding 无法达到同样的效果。

   • 从图 c 可以看到，metapath2vec 能够将每对author-venue pair 对进行紧密的分组，而不是将两种类型的节点分类两列。如 R.E.Tarjan + FOCS、H.Jensen + SIGGRAPH、H.Ishli + CHI、R.Agrawal + SIGMOD 等等。 常规的 embedding 方法也无法达到这种效果。

   • metapath2vec/metapath2vec++ 都可以将来自相似领域的节点放在一起、不同领域的节点相距较远。这种分组不仅反映在 venue 节点上，也反映在 author 节点上。

   

2. 下图通过 t-SNE 可视化了metapath2vec++ 学到的AMiner 数据集不同领域的顶级 CS 会议，一共48 个会议、16个领域，每个领域 3 个会议。

   • 可以看到：来自同一个领域的会议彼此聚在一起，并且不同组之间的间隔比较明显。这进一步验证了 metapath2vec++ 的 embedding 能力。

   • 另外，异质 embedding 能够揭示不同领域的节点之间的相似性。如，右下角的 Core CS 领域的几个簇（计算机系统簇 OSDI、计算机网络簇SIGCOMM、计算机安全簇S&P、计算机架构簇ISCA）、右上角的 Big AI 领域的几个簇（数据挖掘簇 KDD、信息检索簇 SIGIR、AI 簇 AI、机器学习簇 NIPS、NLP 簇 ACL、计算机视觉簇 CVPR）。

   因此，这些可视化结果直观地展示了 metapath2vec++ 的新能力：发现、建模、以及捕获异质网络中多种类型节点之间的底层结构关系和语义关系。

   

1.2.5 可扩展性

1. metapath2vec/metapah2vec ++ 可以使用和 word2vec/node2vec 中相同的机制来并行化。我们对 AMiner 数据集进行实验，实验在 Quad 12(48) core 2.3 GHz Intel Xeon CPUs E7-4850 上进行。我们实现不同的线程数 {1,2,4,8,16,24,32,40} ，每个线程使用一个 CPU core 。

   下面给出了metapath2vec/metapath2vec++ 的加速比。最佳加速比由虚线 $y=x$$y=x$ 表示。我们的这两种方法都可以达到能够接受的亚线性加速比，它们都接近于虚线。具体而言，在使用 16 个 core 时，它们可以实现 11-12 倍的加速比；使用 40 个 core 时，它们可以实现 24-32 倍加速比。

   在使用 40 个 core 时，metapath2vec ++ 的学习过程只需要 9 分组即可训练整个 AMS CS 网络的 embedding ，该网络由 900 万以上的作者、3300 多个 venue、300 万篇论文组成。总体而言，对于具有数百万个节点的大规模异质网络，metapath2vec/metapath2vec++ 是高效的且 scalable 的。